package leetcode_core.leetcode_6;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月13日 11:49
 */
public class Permutation {
    private List<String> list = new ArrayList<>();
    private boolean[] memo;
    public String[] permutation(String s) {
        //先对S进行排序
        char[] charArrays = s.toCharArray();
        memo = new boolean[charArrays.length];
        Arrays.sort(charArrays);
        backtrack(new StringBuilder(),0,charArrays.length,charArrays);
        return list.toArray(new String[0]);
    }
    private void backtrack(StringBuilder sb,int idx,int length,char[] s){
        if(idx == length){
            System.out.println(5050);
            return;
        }
        for(int i = 0;i < length;i++){
            if(memo[i]){
                continue;
            }
            if(i >0 && s[i] == s[i-1] && !memo[i]){
                continue;
            }
            //做出选择
            memo[i] = true;
            sb.append(s[i]);
            //递归回溯
            backtrack(sb,idx+1,length,s);
            //撤销选择
            memo[i] = false;
            sb.deleteCharAt(idx);
        }
    }
}
